import java.util.ArrayList;
import java.util.List;

public class StringSearch {

	/**
	 * Find all instances of pattern in text using Boyer-Moore algorithm.
	 * Use buildBoyerMooreCharTable to build your reference table.
	 * 
	 * @param pattern
	 * The String to find
	 * @param test
	 * The String to look through
	 * @return
	 * A List of starting indices where pattern was found in text
	 */
	public static List<Integer> boyerMoore(String pattern, String text) {
		List<Integer> list = new ArrayList<Integer>();
		int[] map = buildBoyerMooreCharTable(pattern);
		int n = 0;
		if (pattern.length()>text.length()) return list;
		int i;
		while (n+pattern.length()<=text.length()) {
			for (i=pattern.length()-1;i>=0;i--) 
				if (pattern.charAt(i)==text.charAt(n+i)) {
					if (i==0) list.add(n); }
				else break;
			n+=map[text.charAt(n+pattern.length()-1)]; }
		return list; }

	/**
	 * Creates a table of distances from each character to the end.
	 * Has an entry for every character from 0 to Character.MAX_VALUE.
	 * For use with Boyer-Moore.
	 *
	 * If the character is in the string:
	 * 		map[c] = length - last index of c - 1
	 * Otherwise:
	 * 		map[c] = length
	 *
	 * @param pattern
	 * The string being searched for
	 * @return
	 * An int array for Boyer-Moore
	 */
	public static int[] buildBoyerMooreCharTable(String pattern) {  // max 1, (length - last index of c - 1)
		int[] map = new int[Character.MAX_VALUE + 1];

		for (int i=0;i<map.length;i++) 
			map[i] = pattern.length();
		for (int i=0;i<pattern.length();i++) 
			map[pattern.charAt(i)] = max(pattern.length()-pattern.lastIndexOf(pattern.charAt(i))-1,1);
		return map; }

	private static int max(int a, int b){
		if (a>b) return a;
		else return b; }

	/**
	 * Find all instances of pattern in text using Knuth-Morris-Pratt algorithm.
	 * Use buildKmpSuffixTable to build your reference table.
	 * 
	 * @param pattern
	 * The String to find
	 * @param test
	 * The String to look through
	 * @return
	 * A List of starting indices where pattern was found in text
	 */
	public static List<Integer> kmp(String pattern, String text) {		
		List<Integer> list = new ArrayList<Integer>();
		if (pattern.length()>text.length()) return list;
		int[] map = buildKmpSuffixTable(pattern);
		int p=0;
		int t=0;

		while (t<text.length()) {
			while (pattern.charAt(p)!=text.charAt(t)) {
				if (p==0) t++;
				else p=map[p];
				if (t==text.length()) break; }
			if (p==pattern.length()-1) {
				list.add(t-pattern.length()+1);
				p = -1; t = t-pattern.length()+1;}
			p++;t++;}
		return list; }


	/**
	 * Creates a table of matching suffix and prefix sizes.
	 * For use with Knuth-Morris-Pratt.
	 *
	 * If i = 0:
	 * 		map[i] = -1
	 * If i > 0:
	 * 		map[i] = size of largest common prefix and suffix for substring of size i
	 *
	 * @param pattern
	 * The string bing searched for
	 * @return
	 * An int array for Knuth-Morris-Pratt
	 */
	public static int[] buildKmpSuffixTable(String pattern) {
		int[] map = new int[pattern.length()];
		map[0] = -1;
		if (pattern.length()>1)
			map[1] = 0;
		int i = 0; int j = 1;
		
		while (j<pattern.length()-1) 
			if (pattern.charAt(i)==pattern.charAt(j)) {
				map[j+1] = map[j]+1;
				i++; j++; }
			else {
				i=0;
				if (pattern.charAt(i)!=pattern.charAt(j)) map[j+1] = 0;
				else {
					map[j+1] = 1;
					i++; }
				j++; }
		
		return map; }

	// This is the base to be used for Rabin-Karp. No touchy.
	private static final int BASE = 997;

	/**
	 * Find all instances of pattern in text using Rabin-Karp algorithm.
	 * Use hashString and updateHash to handle hashing.
	 *
	 * @param pattern
	 * The String to find
	 * @param test
	 * The String to look through
	 * @return
	 * A List of starting indices where pattern was found in text
	 */
	public static List<Integer> rabinKarp(String pattern, String text) {
		int hashP = hashString(pattern);
		List<Integer> list = new ArrayList<Integer>();
		for (int i=0;i<(text.length()-pattern.length()+1);i++) {
			int hashT = hashString(text.substring(i, i+pattern.length()));
			if (hashP==hashT)
				if (pattern.equals(text.substring(i, i+pattern.length())))
					list.add(i); }
		return list; }

	/**
	 * Hashes a string in a specified way.
	 * For use with Rabin-Karp.
	 *
	 * This hash function will use BASE and the indices of the characters.
	 * Each character at i is multiplied by BASE raised to the power of length - 1 - i
	 * These values are summed to determine the entire hash.
	 *
	 * For example:
	 * Hashing "bunn" as a substring of "bunny" with base 433
	 * hash = b * 433 ^ 3 + u * 433 ^ 2 + n * 433 ^ 1 + n * 433 ^ 0
	 *      = 98 * 433 ^ 3 + 117 * 433 ^ 2 + 110 * 433 ^ 1 + 110 * 433 ^ 0
	 *      = 7977892179
	 *
	 * @param pattern
	 * The String to be hashed
	 * @return
	 * A hash value for the string
	 */
	public static int hashString(String pattern) {
		int hash = 0;
		for (int i=0;i<pattern.length();i++) hash+=(pattern.charAt(i)*exp(BASE,pattern.length()-1-i));
		return hash; }

	private static int exp(int a, int b) {
		int out = 1;
		for (int i=0;i<b;i++) out*=a;
		return out; }

	/**
	 * Updates the oldHash in a specified way.
	 * Follows the same hash formula as hashString.
	 * For use with Rabin-Karp.
	 *
	 * To update the hash, remove the oldChar times BASE raised to the length - 1,
	 * 		multiply by BASE, and add the newChar.
	 * For example:
	 * Shifting from "bunn" to "unny" in "bunny" with base 433
	 * hash("unny") = (hash("bunn") - b * 433 ^ 3) * 433 + y * 433 ^ 0
	 *              = (7977892179 - 98 * 433 ^ 3) * 433 + 121 * 433 ^ 0
	 *              = 9519051770
	 *
	 * @param oldHash
	 * The old hash to be updated
	 * @param newChar
	 * The new character added at the end of the substring
	 * @param oldChar
	 * The old character being removed from the front of the substring
	 * @param length
	 * The length of the hashed substring
	 */
	public static int updateHash(int oldHash, char newChar, char oldChar, int length) {
		return (oldHash-oldChar*exp(BASE,length-1))*BASE+newChar; }
}